package com.zzy.other;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 402. 移掉 K 位数字
 * 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
 * 输入：num = "1432219", k = 3
 * 输出："1219"
 * 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
 */
public class L402removeKdigits {
    public static String removeKdigits(String num, int k) {
        int len = num.length();
        Deque<Character> queue = new LinkedList<>();
        //遍历num
        for (int i = 0;i<len; i++){
            char c = num.charAt(i);
            //使用while是因为队列中有相同的数字罗列在一起，如果k还有剩余，需要把同样的数字一并剔出
            while(k>0 && queue.size()>0 && queue.peek()>c){
                queue.pop();
                k--;
            }
            //防止把前导0放进去
            if(!(queue.isEmpty() && c=='0')){
                queue.push(c);
            }
        }
        //k还有剩余，从最后开始弹出
        while(k>0 && !queue.isEmpty()){
            queue.pop();
            k--;
        }
        if(queue.isEmpty()){
            return "0";
        }else {
            StringBuilder sb = new StringBuilder();
            while(!queue.isEmpty()){
                sb.append(queue.pollLast());
            }
            return sb.toString();
        }
    }
}

